package hash;

import java.util.NoSuchElementException;

/**
 * @Description: 基于开散列下实现的HashMap
 * @Author Stark
 * @Date 2022/3/16 16:12
 **/
public class MyHashMap {
    private class Node{
        int key;
        int value;
        Node next;

        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    //哈希表的元素个数
    private int size;
    //默认哈希表的长度
    private static final int DEFAULT_LENGTH = 16;
    //默认的负载因子
    private static final double LOAD_FACTOR = 0.75;
    //取模数，用于取得key的索引
    private int M;
    //用于存储数据的数组
    Node[] data;

    public MyHashMap(){
        this(DEFAULT_LENGTH);
    }
    public MyHashMap(int length) {
        this.data = new Node[length];
        this.M = length;
    }

    private int hash(int key){
        return key % M;
    }

    /**
     * 添加元素
     * 如果key值存在，则更新value的值，返回以前的value值
     * @param key
     * @param value
     * @return
     */
    public int add(int key,int value){
        int index = hash(key);
        for(Node node = data[index];node != null;node = node.next){
            if(node.key == key){
                int oldValue = node.value;
                node.value = value;
                return oldValue;
            }
        }
        //该索引的位置为null或没有key相同的
        Node newNode = new Node(key,value,data[index]);
        data[index] = newNode;
        size++;
        if(M * LOAD_FACTOR <= size){
            resize();
        }
        return value;
    }

    /**
     * 调整哈希表
     */
    private void resize() {
        int oldM = M;
        M <<= 1;
        Node[] newData = new Node[M];
        for (int i = 0; i < oldM; i++) {
            if(data[i] == null){
                continue;
            }else {
                for (Node node = data[i];node != null;){
                    Node tmp = node.next;
                    int index = hash(node.key);
                    node.next = newData[index];
                    newData[index] = node;
                    node = tmp;
                }
            }
        }
        data = newData;
    }

    /**
     * 删除与key匹配的键值对，返回value的值
     * @param key
     * @return
     */
    public int remove(int key){
        int index = hash(key);
        if(data[index] == null){
            throw new NoSuchElementException("Does not exist this key");
        }
        //判断头节点是否是待删除结点
        Node node = data[index];
        if(node.key == key){
            int retValue = node.value;
            data[index] = node.next;
            node.next = node = null;
            size--;
            return retValue;
        }
        //当前链表的头结点不是待删除结点
        while(node.next != null){
            if(node.next.key == key){
                Node cur = node.next;
                int retValue = cur.value;
                node.next = cur.next;
                cur.next = cur = null;
                size--;
                return retValue;
            }
            node = node.next;
        }
        throw new NoSuchElementException("Does not exist this key");
    }

    /**
     * 判断key是否存在
     * @param key
     * @return
     */
    public boolean containsKey(int key){
        int index = hash(key);
        for(Node node = data[index];node != null;node = node.next){
            if(node.key == key){
                return true;
            }
        }
        return false;
    }

    /**
     * 判断value是否存在
     * @param value
     * @return
     */
    public boolean containsValue(int value){
        for(int i = 0;i < M;i++){
            for(Node node = data[i];node != null;node = node.next){
                if(node.value == value){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 根据key返回value
     * @param key
     * @return
     */
    public int get(int key){
        int index = hash(key);
        for(Node node = data[index];node != null;node = node.next){
            if(node.key == key){
                return node.value;
            }
        }
        throw new NoSuchElementException("Does not exist this key");
    }

    /**
     * 返回元素的个数
     * @return
     */
    public int size(){
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < M;i++){
            boolean flag = true;
            for(Node node = data[i];node != null;node = node.next){
                sb.append("key:").append(node.key).append(",value:").append(node.value).append(' ');
                flag = false;
            }
            if(flag){
                sb.append("NULL");
            }
            if(i != M - 1) {
                sb.append("\n");
            }
        }
        return sb.toString();
    }
}
